package cn.handong.tool.algorithm.BFS;
/**
 * 广度优先搜索（Breadth First Search , BFS）遍历类似于树的按层次遍历的过程
 * 当碰到岔道口时，总是先依次访问从该岔道口能直接到达的所有结点，
 * 然后再按这些结点被访问的顺序去依次访问它们能直接到达的所有结点，以此类推，直到所有结点都被访问为止。
 *
 * 广度优先搜索一般由队列实现，总是按层次进行遍历
 * 基本写法如下
 * void bfs(int s){
 * 	Queue<Integer> queue=new LinkedList<Integer>();
 * 	queue.offer(s);
 * 	while(!queue.isEmpty()){
 *       //取出队首元素top
 * 	     //访问队首元素top
 * 	     //将队首元素出队
 * 	     //将top的下一层结点中未曾入队的结点全部入队，并设置为已入队
 *   }
 * }
 */

import java.util.LinkedList;
import java.util.Queue;

/**
 * 岛屿问题
 * 给出一个n*m的矩阵，矩阵中的元素为0或1。称位置(x,y)与其上下左右四个位置(x,y+1)、(x,y-1)、(x+1,y)、(x-1,y)是相邻的。
 * 如果矩阵中有若干个1是相邻的（不必两两相邻），那么称这些1构成了一个“块”。求给定的矩阵中“块”的个数。
 * 0 1 1 1 0 0 1
 * 0 0 1 0 0 0 0
 * 0 0 0 0 1 0 0
 * 0 0 0 1 1 1 0
 * 1 1 1 0 1 0 0
 * 1 1 1 1 0 0 0
 */

class 岛屿问题 {
    static Node node=new Node();
    static int[][] a;//01矩阵
    //增量数组，组合分别代表上下右左
    static int[] X = {0,0,1,-1};
    static int[] Y = {1,-1,0,0};
    //BFS函数访问位置(x,y)所在的块，将该块中所有 1 都置为 0
    static void bfs(int x,int y,int n,int m){
        Queue<Node> queue= new LinkedList<>();//定义队列
        node.x=x;
        node.y=y;
        queue.offer(node);//结点入队
        while(!queue.isEmpty()){
            Node top=queue.poll();//返回队首元素并将其出队
            for(int i=0;i<4;i++){
                int newX=top.x+X[i];
                int newY=top.y+Y[i];
                if(newX < n && newX >= 0 && newY < m && newY >= 0 && a[newX][newY] == 1){//如果新位置(newX,newY)需要访问
                    Node newNode=new Node();//设置node的坐标为(newX,newY)
                    newNode.x = newX;
                    newNode.y = newY;
                    queue.offer(newNode);//将node加入对列
                    a[newX][newY] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        a = new int[][] {{0,1,1,1,0,0,1},
                         {0,0,1,0,0,0,0},
                         {0,0,0,0,1,0,0},
                         {0,0,0,1,1,1,0},
                         {1,1,1,0,1,0,0},
                         {1,1,1,1,0,0,0}};
        int n = a.length;
        int m = a[0].length;
        int ans=0;//岛屿个数
        for(int i=0;i<n;i++){//枚举每一个位置
            for(int j=0;j<m;j++){
                if(a[i][j]==1){//如果元素为1且未入队
                    ans++;//岛屿个数加1
                    bfs(i,j,n,m);//访问整个块，将该块所有 "1"的inq都标记为true
                }
            }
        }
        System.out.println(ans);
    }
}
class Node{
    int x,y;//位置(x,y)
}